Gauss Theorem.

     If the GCD(a, b) = d, then there exist such integers x and y, that ax + by = d.

     Proof. From the last but one equation, led out when proving the rightness of Euclid algorithm, we have

a_n = a_n-2 - a_n-1q_n-1.

     Substituting, one after another, the values of

a_k = a_k-2 - a_k-1q_k-1

for k = n-1, n-2, ..., 3, 2, in the end we'll get the expression of the following kind

a_n = a₀ x + a₁ y,

where x and y - some integers, what was to be proved.

     Corollary. If the prime number p divides the product of two numbers a and b, then p divides at least one of the multipliers.

     Proof. Let's assume, a isn't divisible by p, then a and p are co-prime numbers and by force of the above-mentioned theorem, there exist such integers x and y, that ax + py = 1. Multiplying both parts of this equality by b, get abx + bpy = b. In the left part of this equality both addenda are multiple to p : the first according to the condition, and the second contains p as a multiple in the evident form. Consequently, their sum, equal to b, is divisible by p either, what was to be proved.